#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define HASHSIZE 101

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

static struct nlist *hashtab[HASHSIZE]; /* pointer table */

struct nlist *install(char *, char *);
struct nlist *lookup(char *);
unsigned hash(char *); 

int main()
{
    char *name1 = "IN";
    char *text1 = "1";
    char *name2 = "OUT";
    char *text2 = "0";
    char *text3 = "2";

    install(name1, text1);
    install(name2, text2);
    //install(name2, text3);

    printf("The replacement text of defined name %s is %s.\n", name1, lookup(name1)->defn);
    printf("The replacement text of defined name %s is %s.\n", name2, lookup(name2)->defn);

    char name[15], defn[15];
    int install_number;

    scanf("%d", &install_number);

    while(install_number--) {
        scanf("%s%s", name, defn);
        install(name, defn);
    }

    while(scanf("%s", name) != EOF) {
        struct nlist * p = lookup(name);
        if(p == NULL)
            printf("not found\n");
        else
            printf("%s\n", p->defn);
    }

    return 0;
}



/* Please write the function */
char *strdup_my(char *s)
{
    int l=strlen(s);
    char * ans=malloc(l+1);
    strcpy(ans,s);
    return ans;
}
struct nlist *talloc(void)
{
    struct nlist * node=malloc(sizeof(struct nlist));
    node->next=NULL;
    node->name=NULL;
    node->defn=NULL;
    return node;
}
unsigned hash(char * s)
{
    unsigned ans=0;
    while(*s)ans+=*s,++s;
    return ans%HASHSIZE;
}
struct nlist *install(char *name, char * defn)
{
    unsigned h=hash(name);
    struct nlist * now=hashtab[h];
    while(1)
    {
        if(!now)
        {
            now=talloc();
            now->name=strdup_my(name);
            now->defn=strdup_my(defn);
            now->next=hashtab[h];
            hashtab[h]=now;
            return now;
        }
        else
        {
            if(strcmp(name,now->name)==0)
            {
                now->defn=strdup_my(defn);                
                return now;
            }
            else
                now=now->next;
        }
    }
    return NULL;
}

struct nlist *lookup(char * name)
{
    unsigned h=hash(name);
    struct nlist * now=hashtab[h];
    while(1)
    {
        if(!now)
            return NULL;
        else
        {
            if(strcmp(name,now->name)==0)
                return now;
            else
                now=now->next;
        }
    }
    return NULL;
}


